package org.lql.algo.codecrush.week004;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:48
 * @description: LCR 148. 验证图书取出顺序 <a href="https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/description/">...</a>
 **/
public class ValidateBookSequences {

	/**
	 * 现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照 一定 的顺序 放入 和 拿取 书籍。
	 * <p>
	 * 给定一个表示图书放入顺序的整数序列 putIn，请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：putIn = [6,7,8,9,10,11], takeOut = [9,11,10,8,7,6]
	 * 输出：true
	 * 解释：我们可以按以下操作放入并拿取书籍：
	 * push(6), push(7), push(8), push(9), pop() -> 9,
	 * push(10), push(11),pop() -> 11,pop() -> 10, pop() -> 8, pop() -> 7, pop() -> 6
	 * 示例 2：
	 * <p>
	 * 输入：putIn = [6,7,8,9,10,11], takeOut = [11,9,8,10,6,7]
	 * 输出：false
	 * 解释：6 不能在 7 之前取出。
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * 0 <= putIn.length == takeOut.length <= 1000
	 * 0 <= putIn[i], takeOut < 1000
	 * putIn 是 takeOut 的排列。
	 */
	public boolean validateBookSequences(int[] putIn, int[] takeOut) {
		Deque<Integer> stack = new ArrayDeque<>();
		int j = 0; // 指向 takeOut 当前要取出的书籍

		for (int book : putIn) {
			stack.push(book); // 模拟放书（入栈）

			// 如果栈顶的书正好是当前要取的书，就取出（出栈）
			while (!stack.isEmpty() && stack.peek() == takeOut[j]) {
				stack.pop();
				j++;
			}
		}

		// 最后看是否所有书都能按照 takeOut 顺序取出
		return stack.isEmpty();
	}

	public static void main(String[] args) {
		int[] putIn = new int[]{6, 7, 8, 9, 10, 11};
		int[] takeOut = new int[]{9, 11, 10, 8, 7, 6};
		System.out.println(new ValidateBookSequences().validateBookSequences(putIn, takeOut));
	}
}
